﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingSpace
{
    class mergeSort : Sorting
    {
        int[] values;

        public mergeSort(int[] values) { this.values = (int[])values.Clone(); }

        public void Sort() { values = Sort(this.values); }

        int[] Sort(int[] arr)
        {
            int len = arr.Length;
            if (len <= 1) return arr;
            
            int[] leftpart = Sort(arr[0..(len/2)]), rightpart = Sort(arr[(len / 2)..len]), res = new int[len];
            int n = 0, m = 0, k = 0;

            while (n < leftpart.Length && m < rightpart.Length)
            {
                if (leftpart[n] <= rightpart[m]) res[k++] = leftpart[n++];
                else res[k++] = rightpart[m++];
            }
            while (n < leftpart.Length) { res[k++] = leftpart[n++]; }
            while (m < rightpart.Length) { res[k++] = rightpart[m++]; }

            return res;
        }

        public int[] getValues() { return values; }

        public string getName() { return "Merge sort"; }
    }
}
